package com.singzi.leetcode.N1100;

public class T1005 {
    public static void main(String[] args) {
        Solution1005 solution1005 = new Solution1005();
        int []nums = {3,-1,0,2};
        System.out.println(solution1005.largestSumAfterKNegations1(nums, 3));
    }


}
class Solution1005 {
    public int largestSumAfterKNegations1(int[] nums, int k) {

        int[] index = new int[k];
        for (int i = 0; i < k; i++) {
            index[i] = 999;

        }
        int[] indexOfNums = new int[k];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            insertNums(index, nums[i],i,indexOfNums);
            sum += nums[i];
        }
        int subSum = 0;
        for (int i = 0; i < k; i++) {
            subSum +=nums[indexOfNums[i]];
        }

        return sum - 2*subSum;

    }
    public void insertNums(int[] nums, int num, int index, int []indexOfNums){
        if(num > nums[0]) return;

        for (int i = 1; i < nums.length; i++) {
            if(num > nums[i]){
                for(int j = 0;j < i-1;j++){
                    nums[j] = nums[j+1];
                    nums[i-1] = num;
                    indexOfNums[i-1] = index;
                }
                break;
            }
        }


    }
}